<script>

class Node{
    constructor (data){
        this.left = null
        this.right = null
        this.value = data
    }
}

class Tree{
    constructor (){
        this.root = null
    }
    //根据父节点插入一个新节点
    insertByFather(node, newNode) {
        //如果新节点value小于父节点value，则插入父节点左子树上，否则插入右子树上
        if(newNode.value < node.value){
            //如果父左子树存在，则递归判断插入，否则新节点就是父左子节点
            if(node.left){
                insertByFather(node.left, newNode)
            }else{
                node.left = newNode
            }
        }else{
            if(node.right){
                insertByFather(node.right, newNode)
            }else{
                node.right = newNode
            }
        }
    }
    insert(value){
        let node = new Node(value)
        if(this.root){
            insertNode(this.root, node)
        }else{
            this.root = node
        }
    }
    
    removeNode(root, value){
        if(!root){
            return null
        }
        if(value < root.value){
            removeNode(root.left, value)
        }else if(value > root.value){
            removeNode(root.right, value)
        }else{
            if(!root.left && !root.right){
                root = null
            }else if(root.left && root.right){
                let rightMinNode = findMinNode(root.right)
                root.value = rightMinNode.value
                this.removeNode(root.right, rightMinNode.value)
            }else{
                root = root.left || root.right
            }
        }
    }
    findMinNode(root){
        if(root.left){
            findMinNode(root.left)
        }else{
            return root
        }
    }
    //前序遍历
    preOrder(node){
        if(node){
            console.log(node.valu)
            this.preOrder(node.left)
            this.preOrder(node.right)
        }
    }
    //中序遍历
    inOrder(node){
        if(node){
            this.midOrder(node.left)
            console.log(node.value)
            this.midOrder(node.right)
        }
    }
    //后序遍历
    postOrder(node){
        if(node){
            this.postOrder(node.left)
            this.postOrder(node.right)
            console.log(node.value)
        }
    }
}




</script>